package day230326;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/3/26 21:15
 * 括号匹配问题
 */
public class Parenthesis {

    // 判断长度为 n 的括号序列 s 是否为合法括号
    public boolean chkParenthesis(String s, int n) {
        if ((n & 1) == 1) {
            // 如果括号匹配, 一定 n 是偶数, 奇数, 一定不符合
            return false;
        }
        // 使用栈去模拟
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                // 左括号直接入栈
                stack.push(c);
            } else {
                // 右括号
                if (stack.isEmpty()) {
                    // 遇到右括号时, 如果栈空, 则一定不匹配
                    return false;
                } else if (stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false; // 说明字符串 s 有误
                }
            }
        }
        // 遍历完整个 s 后, 如果是匹配的, 栈一定是空的
        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}
